/*
Source : https://leetcode.com/problems/set-matrix-zeroes/
Author : nflush@outlook.com
Date   : 2016-06-27
*/
/*
73. Set Matrix Zeroes
Total Accepted: 69729 Total Submissions: 205903 Difficulty: Medium

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Subscribe to see which companies asked this question
*/
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = n > 0?matrix[0].size():0;
        vector <int>rows;
        vector <int>cols;
        for (int i = 0; i<n;i++){
            for (int j = 0;j<m;j++){
                if (matrix[i][j] == 0){
                    rows.push_back(i);
                    cols.push_back(j);
                }
            }
        }
        std:sort(cols.begin(), cols.end());
        for(int i=0;i<rows.size();i++){
            int row = rows[i];
            for (int j=0;j<m;j++){
                matrix[row][j]=0;
            }
        }
        for (int j=0;j<cols.size();j++){
            int col = cols[j];
            for(int i=0;i<n;i++){
                matrix[i][col]=0;
            }
        }
    }
};

